#include <iostream>
#include <memory>
#include <typeinfo>
#include <new>
#include <bitset>
#include <cassert>
#include <string>
#include <sstream>
#include <cstdlib>
#include <sys/time.h>

//void * operator new(std::size_t size) {
//	//return (void *) 0;
//	return ::operator new(size);
//}

namespace leo {

using std::size_t;
using std::ptrdiff_t;

template<size_t N_STR, size_t M_STR_LEN>
class ssmem_pool {
public:
	ssmem_pool() :
			first_empty(0) {
	}

	char* find_first_not_used_string() throw(std::bad_alloc) {
		if (first_empty < N_STR) {
			state[first_empty] = true;
			char* ptr = &array[first_empty].str[0];
			do {
				++first_empty;
			} while (first_empty < N_STR && state[first_empty] == true);
			return ptr;
		}
		throw std::bad_alloc();
	}
inline void return_back_string(char * ptr) {
		char* start_address = &array[0].str[0];
		ptrdiff_t diff = ptr - start_address;
		size_t index_of_str = diff / sizeof(str_type);
		state[index_of_str] = false;
		if (index_of_str < first_empty)
		{
			first_empty = index_of_str;
		}
	}

inline size_t max_size() const {
		return M_STR_LEN;
	}
	// print all strings table
	template<size_t N_STR1, size_t M_STR_LEN1>
	friend std::ostream& operator<<(std::ostream& out,
			const ssmem_pool<N_STR1, M_STR_LEN1>& obj);
private:
	struct str_type {
		char str[M_STR_LEN];
	};

	str_type array[N_STR];
	std::bitset<N_STR> state;
	size_t first_empty;
};

template<size_t N_STR, size_t M_STR_LEN>
std::ostream& operator<<(std::ostream& out,
		const ssmem_pool<N_STR, M_STR_LEN>& obj) {
	out << "---Stack-String-Table---------------------------------------";
	out << std::endl;
	for (size_t i = 0; i < N_STR; ++i) {
		if (obj.state[i]) {
			size_t string_rep_size = sizeof(size_t) * 3; // test only
			const char * c = &obj.array[i].str[string_rep_size];
			out << c;
			out << std::endl;
		}
	}
	out << "---Stack-String-Table---------------------------------------";
	out << std::endl;
	return out;
}

typedef leo::ssmem_pool<16, 1024> local_stack_pool_t;

local_stack_pool_t *g_string_mem_pool = NULL;

template<typename _Tp>
class string_stack_allocator {
public:
	typedef size_t size_type;
	typedef ptrdiff_t difference_type;
	typedef _Tp* pointer;
	typedef const _Tp* const_pointer;
	typedef _Tp& reference;
	typedef const _Tp& const_reference;
	typedef _Tp value_type;

	template<typename _Tp1>
	struct rebind {
		typedef string_stack_allocator<_Tp1> other;
	};

	string_stack_allocator() throw () {
	}

	string_stack_allocator(const string_stack_allocator&) throw () {
	}

	template<typename _Tp1>
	string_stack_allocator(const string_stack_allocator<_Tp1>&) throw () {
	}

	~string_stack_allocator() throw () {
	}

	pointer address(reference __x) const {
		return &__x;
	}

	const_pointer address(const_reference __x) const {
		return &__x;
	}

	pointer allocate(size_type __n, const void* = 0) {
		if (__n > this->max_size())
			throw std::bad_alloc();
		//return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
		return g_string_mem_pool->find_first_not_used_string();
	}

	// __p is not permitted to be a null pointer.
	void deallocate(pointer __p, size_type __n) {
		//::operator delete(__p);
		g_string_mem_pool->return_back_string(__p);
	}

	size_type max_size() const throw () {
		return g_string_mem_pool->max_size(); //size_t(-1) / sizeof(_Tp);
	}

	void construct(pointer __p, const _Tp& __val) {
		::new ((void *) __p) _Tp(__val);
	}

	void destroy(pointer __p) {
		__p->~_Tp();
	}
};

template<typename _Tp>
inline bool operator==(const string_stack_allocator<_Tp>&, \
		const string_stack_allocator<_Tp>&) {
	return true;
}

template<typename _Tp>
inline bool operator!=(const string_stack_allocator<_Tp>&, \
		const string_stack_allocator<_Tp>&) {
	return false;
}

typedef std::basic_string<char, std::char_traits<char>, \
		leo::string_stack_allocator<char> > string;

typedef std::basic_stringstream<char, std::char_traits<char>, \
		leo::string_stack_allocator<char> > stringstream;
}

leo::string test_stack_alloc_funct(int number, const char * prefix)
{
	leo::stringstream ss;
	ss << prefix << number << " some additional string for test ";
	leo::string str = ss.str();
	leo::stringstream ssnum;
	ssnum << __LINE__;
	str += ssnum.str() + ss.str();
	return str;
}

std::string test_new_alloc_funct(int number, const char * prefix)
{
	std::stringstream ss;
	ss << prefix << number << " some additional string for test ";
	std::string str = ss.str();
	std::stringstream ssnum;
	ssnum << __LINE__;
	str += ssnum.str() + ss.str();
	return str;
}

void one_test(const int iterations) {
	std::cout << "current iteration count " << iterations << std::endl;
	std::srand(time(NULL));
	{
		timeval start, end;
		int i = iterations;
		gettimeofday(&start, NULL);
		const char* prefix = "small";
		const char* prefix2 = "test stack alloc string other prefix different" \
"большая строка большая строка большая строка большая строка большая строка ";
		const char* test_prefix = std::rand() % 2 == 1 ? prefix : prefix2;
		leo::string result;
		while (i > 0) {
			result = test_stack_alloc_funct(i, test_prefix);
			i--;
		};
		gettimeofday(&end, NULL);
		double tS = start.tv_sec + (start.tv_usec / 1000000.0);
		double tE = end.tv_sec + (end.tv_usec / 1000000.0);
		double secons = tE - tS;
		std::cout << " sec: " << std::fixed << secons << std::endl;
	}
	{
		timeval start, end;
		gettimeofday(&start, NULL);
		int i = iterations;
		const char* prefix = "small";
		const char* prefix2 = "test stack alloc string other prefix different" \
"большая строка большая строка большая строка большая строка большая строка ";
		const char* test_prefix = std::rand() % 2 == 1 ? prefix : prefix2;
		std::string result;
		while (i > 0) {
			result = test_new_alloc_funct(i, test_prefix);
			i--;
		};
		gettimeofday(&end, NULL);
		double tS = start.tv_sec + (start.tv_usec / 1000000.0);
		double tE = end.tv_sec + (end.tv_usec / 1000000.0);
		double secons = tE - tS;
		std::cout << " sec: " << std::fixed << secons << std::endl;
	}
}

int main() {
//	std::cout << "sizeof(size_t) = " << sizeof(size_t) << std::endl;
	leo::local_stack_pool_t string_mem_pool;
	leo::g_string_mem_pool = &string_mem_pool;
//	leo::string str("");
//	str += "1";
//	str += "string of 13";
//	std::cout << str << std::endl;
//	std::cout << string_mem_pool;
//	leo::string second = (str + " Hello from English! 24").c_str();
//	leo::stringstream ss;
//	assert(ss);
//	ss << "add simple string and number of current line: ";
//	assert(ss);
//	ss << __LINE__;
//	assert(ss);
//	std::cout << ss.str() << std::endl;
//	second = second + ss.str();
//	std::cout << second << std::endl;
//	std::cout << string_mem_pool;
//	{
//		leo::string other_str("some other string ...... words .... words....");
//		std::cout << other_str << std::endl;
//		std::cout << string_mem_pool;
//	}
//	std::cout << string_mem_pool;
//	std::cout << second << std::endl;
	const int iterations = 5;
	for (int i = 0, current_iter = iterations; \
		i < 23; \
		i++, current_iter *= 2)
	{
		one_test(current_iter);
	}

	return 0;
}
